
import java.util.*;
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class project {
    List<Integer> list=new ArrayList<>();
    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        dfs(root1);
        dfs(root2);
        Collections.sort(list);
        return list;
    }
    public void dfs(TreeNode root){
        if(root==null){
            return ;
        }
        list.add(root.val);
        dfs(root.left);
        dfs(root.right);
    }













    public int[][] imageSmoother(int[][] img) {
        int row=img.length;
        int col=img[0].length;
        int[][] arr=new int[row][col];
        int count=0;
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                count=0;
                for(int prevI=i-1;prevI<=i+1;prevI++){
                    for(int prevJ=j-1;prevJ<=j+1;prevJ++){
                        if(prevI>=0&&prevJ>=0&&prevI<row&&prevJ<col){
                            arr[i][j]+=img[prevI][prevJ];
                            count++;
                        }
                    }
                }
                arr[i][j]/=count;
            }
        }
        return arr;
    }













    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        dfs1(image,sr,sc,newColor,image[sr][sc]);
        return image;
    }
    public void dfs1(int[][] arr,int sr,int sc,int newColor,int color){
        if(sr<0||sc<0||sr>= arr.length||sc>=arr[0].length||newColor==color||arr[sr][sc]!=color){
            return ;
        }
        arr[sr][sc]=newColor;
        dfs1(arr,sr+1,sc,newColor,color);
        dfs1(arr,sr-1,sc,newColor,color);
        dfs1(arr,sr,sc+1,newColor,color);
        dfs1(arr,sr,sc-1,newColor,color);
    }











    public int[] maxSubsequence(int[] nums, int k) {
        int[] arr= Arrays.copyOf(nums,nums.length);
        Arrays.sort(arr);
        Map<Integer,Integer> map=new HashMap<>();
        for(int i=arr.length-1;i>=arr.length-k;i--){
            map.put(arr[i],map.getOrDefault(arr[i],0)+1);
        }
        int[] ret=new int[k];
        int j=0;
        for(int i=0;i<nums.length;i++){
            if(map.getOrDefault(nums[i],0)>0){
                ret[j++]=nums[i];
                map.put(nums[i],map.get(nums[i])-1);
                if(j==k){
                    break;
                }
            }
        }
        return ret;
    }














    public int maxDistance(int[] colors) {
        int max=0;
        for(int i=0;i<colors.length/2;i++){
            for(int j=colors.length-1;j>i;j--){
                if(colors[i]!=colors[j]){
                    max=Math.max(j-i,max);
                }
            }
        }
        return max;
    }
















    public int orchestraLayout(int num, int xPos, int yPos) {
        int[][] arr=new int[num][num];
        int index=1;
        int row=0;
        int col=num;
        int left=0;
        int right=num;
        while (row<col&&left<right){
            for(int i=row;i<col;i++){
                arr[row][i]=index;
                index++;
                index=index==10?1:index;
            }
            for(int i=left+1;i<right;i++){
                arr[i][right]=index;
                index++;
                index=index==10?1:index;
            }
            for(int i=right-2;i>left;i--){
                arr[right][i]=index;
                index++;
                index=index==10?1:index;
            }
            for(int i=col-2;i>row;i--){
                arr[i][row]=index;
                index++;
                index=index==10?1:index;
            }
            row++;
            col--;
            left++;
            right--;
        }
        return arr[xPos][yPos];
    }
















    public int maxScore(String s){
        int max=s.charAt(0)=='0'?1:0;
        for(int i=1;i<s.length();i++){
            if(s.charAt(i)=='1'){
                max++;
            }
        }
        int index=max;
        for(int i=1;i<s.length()-1;i++){
            if(s.charAt(i)=='0'){
                index++;
            }else{
                index--;
            }
            max=Math.max(index,max);
        }
        return max;
    }
















    public String reformat(String s) {
        char[] nums=s.toCharArray();
        int math=0;
        int english=0;
        for(int i=0;i<nums.length;i++){
            if(nums[i]>='0'&&nums[i]<='9'){
                math++;
            }else{
                english++;
            }
        }
        if(Math.abs(math-english)>1){
            return "";
        }
        if(math>english){
            math=0;
            english=1;
        }else{
            math=1;
            english=0;
        }
        for(char ch : s.toCharArray()){
            if(ch>='0'&&ch<='9'){
                nums[math]=ch;
                math+=2;
            }else{
                nums[english]=ch;
                english+=2;
            }
        }
        return new String(nums);
    }














    public boolean isPathCrossing(String path) {
        Set<String> set=new HashSet<>();
        String str="0,0";
        set.add(str);
        int row=0;
        int col=0;
        for(int i=0;i<path.length();i++){
            char ch=path.charAt(i);
            switch(ch){
                case 'N':
                    row++;
                    break;
                case 'E':
                    col++;
                    break;
                case 'S':
                    row--;
                    break;
                case 'W':
                    col--;
                    break;
            }
            str=row+","+col;
            if(set.contains(str)){
                return true;
            }
            set.add(str);
        }
        return false;
    }













    public int countBattleships(char[][] board) {
        int count=0;
        int row=board.length;
        int col=board[0].length;
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(board[i][j]=='X'){
                    if((i<=0||board[i-1][j]!='X')&&(j<=0||board[i][j-1]!='X')){
                        count++;
                    }
                }
            }
        }
        return count;
    }
}
